package class1;

import cn.hutool.core.util.ArrayUtil;


/**
 * 大根堆 与 小根堆
 * 大根堆：[9, 7, 3, 6, 5, 2, 0]
 * +
 * <p>
 * 小根堆：[]
 */
public class Code09_HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 6, 8, 4, 5, 7};
        heapSort(arr);
        System.out.println(ArrayUtil.toString(arr));
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 调整成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        // 先调整一次
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize); // 进行调整将变成大根堆
            swap(arr, 0, --heapSize);   // 调整后与末尾交换
        }
    }

    /**
     * 7
     * 4 6
     * 13 25
     */
    // 新加进来的数，现在停在了index位置，请以此往上移动
    // 插入需要上浮
    public static void heapInsert(int[] arr, int index) {
        // index: 为当前节点
        // (index - 1)>>1: 为父节点
        // index ==0时，arr[0] 与 arr[(0-1)/2]比较，并不成立
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 下沉
    // 从index位置往下看，不断下沉
    // 停：夹带的孩子都不再比index位置的数大；已经没孩子了
    // heapSize为界限
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = (index << 1) | 1; // 左孩子的值

        // 只需判断左孩子是否越界，因为完全二叉树，左孩子如果越界，右孩子一定越界
        while (left < heapSize) {
            // 1.判断：右孩子不越界 left + 1 < heapSize
            // 2.判断：右孩子大于左孩子 arr[left + 1] > arr[left]
            // 3.将较大的值赋给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            // index与较大子节点进行比较
            largest = arr[largest] > arr[index] ? largest : index;

            if (largest == index) {
                return;
            }
            // index和较大孩子交换位置
            swap(arr, largest, index);
            index = largest; // 来到子节点
            left = (index << 1) | 1; // 重新计算左子节点
        }
    }

    public static void swap(int[] arr, int x, int y) {
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }
}
